package com.LeetCode.BFS;

import org.junit.Test;

import java.util.PriorityQueue;

/**
 * 接雨水 Ⅱ  3d接雨水
 */
public class trapRainWaterⅡ {
    public int trapRainWater(int[][] heights) {
        if(heights == null || heights.length == 0) return 0;
        int n = heights.length;
        int m = heights[0].length;

        boolean[][] visit = new boolean[n][m];

        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);


        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(i == 0 || j == 0 || i == n-1 || j == m-1){
                    heap.offer(new int[]{i,j,heights[i][j]});
                    visit[i][j] = true;
                }
            }
        }

        int[] dirs = {-1,0,1,0,-1};
        int res = 0;
        while(!heap.isEmpty()){
            int[] poll = heap.poll();
            for(int k = 0 ; k < 4; k++){
                int nx = poll[0] + dirs[k];
                int ny = poll[1] + dirs[k+1];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visit[nx][ny]){
                    if(poll[2] > heights[nx][ny]){
                        res += poll[2] - heights[nx][ny];
                    }

                    heap.offer(new int[]{nx,ny,Math.max(poll[2] , heights[nx][ny])});
                    visit[nx][ny] = true;
                }
            }
        }
        return res;
    }

    @Test
    public void test(){
        int[][] heights = {
                {1,4,3,1,3,2},
                {3,2,1,3,2,4},
                {2,3,3,2,3,1}
        };
        System.out.println(trapRainWater(heights));
    }
}














